package Top200;

import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-02-23 9:48
 */
public class totalNQueens52 {
    int res=0;
    void backtrack(int n, LinkedList<String> path,int row){
        if (row==n){
            res++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!isvalid(n,path,row,i)) continue;
            StringBuffer sb=new StringBuffer();
            for (int j = 0; j < n; j++) {
                if (j==i){
                    sb.append('Q');
                }else {
                    sb.append('.');
                }
            }
            path.add(sb.toString());
            backtrack(n,path,row+1);
            path.removeLast();
        }
    }

    boolean isvalid(int n,LinkedList<String> path,int row,int col){
        for (int i = 0; i < path.size(); i++) {
            if (path.get(i).charAt(col)=='Q') return false;
        }
        for (int i = row-1,j=col-1; i >=0&&j>=0 ; i--,j--) {
            if (path.get(i).charAt(j)=='Q') return false;
        }
        for (int i = row-1,j=col+1; i >=0&&j<n ; i--,j++) {
            if (path.get(i).charAt(j)=='Q') return false;
        }
        return true;
    }
    public int totalNQueens(int n) {
        backtrack(n,new LinkedList<>(),0);
        return res;
    }
}
